#include "headfiles.h"

using namespace std;

// in this function, n has two children, so we just
// need to find the left most child of its right subtree
NODE * findInOrderNextNode(NODE *n) {
	if (n == NULL) {
		return NULL;
	}

	NODE *child = n->right;
	while (child->left) {
		child = child->left;
	}

	return child;
}

// Three scenarios:
// 1. n is the leaf, just delele itself
// 2. n has one child, easy to delete, put its child as a child  of its parent
// 3. n has two children, find its previous or next in-order node. 
//    replace n's value with that node's value, and delete that node.
//    We are sure that the next node has at most one child, and can be 
//    deleted with the approach in scenario 1 or 2.

bool deleteBinSearchTreeNode(NODE *n) {
	if (n == NULL) {
		cout << "Node to be deleted is NULL!" << endl;
		return true;
	}

	if (n->left && n->right) {
		NODE *next = findInOrderNextNode(n);
		if (next == NULL) {
			cout << "Wrong, n must have an in-order next node!" << endl;
			return false;
		}

		n->i = next->i;
		NODE *p = next->p;
		if (p->left == next) {
			if (next->left) {
				p->left = next->left;
			}
			else if (next->right) {
				p->left = next->right;
			}
			else {
				p->left = NULL;
			}
		}
		// next is a right side 
		else {
			if (next->left) {
				p->right = next->left;
			}
			else if (next->right) {
				p->right = next->right;
			}
			else {
				p->right = NULL;
			}
		}
	}
	// n has 0 or one child
	else {
		NODE *p = n->p;
		if (p->left == n) {
			if (n->left) {
				p->left = n->left;
			}
			else if (n->right) {
				p->left = n->right;
			}
			else {
				p->left = NULL;
			}
		}
		// n is a right side 
		else {
			if (n->left) {
				p->right = n->left;
			}
			else if (n->right) {
				p->right = n->right;
			}
			else {
				p->right = NULL;
			}
		}
	}
	
	return true;
}

